package binarySearch;

/*
* 插值查找
* */

public class DifSearch {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        int i = diffSearch(nums, 0, 8, 1);
        System.out.println("索引"+i);
    }

    public static int diffSearch(int[] nums,int left,int right,int target){
        System.out.println("test");
        if (left > right || target < nums[left] ||target>nums[right]){
            return -1;
        }

        int mid = left +(right - left)*(target - nums[left])/(nums[right] - nums[left]);
        if (target > nums[mid]){
            return diffSearch(nums, mid + 1, right, target);
        }else if(target < nums[mid]){
            return diffSearch(nums, left, mid - 1, target);
        }else {
            return mid;
        }
    }
}
